"""
5. 一组数中有一种数出现k次， 其他数都出现了M次， M > 1, k < M。
    找到， 出现了k次的数，
    要求，额外空间复杂度O(1), 时间复杂度O(N)
解析:
    1.将数字转换为 2 进制
    2.对每一位上是1的进行记录
    3.如果某一位上1的个数不是M的整数被，就说明出现K次的这个数这一位上是1.
    4. 把这个位置的1 放到结果上
    例如： 
    [ 3, 15, 15 ]
    0 0 1 1
    1 1 1 1
    1 1 1 1
    
    M = 2
    k = 1
    t -> 2 2 3 3
    
    记录到 ans: ...00000000
    有的位置就是： ...00 11
    出现k次的数就是： 3
"""
import random


def find_k(arr, M):
    # 0 ... 32 代表二进制 最到低 位到最高位, 因为 int 是用32位二进制表达的
    t: list = [ 0 for i in range(32)]
    for val in arr:
        for i in range(32):
            # val >> i 二进制右移i位， 011 右移 1位 01
            # & 1 看这一位是不是 1
            t[i] += (val >> i) & 1
    ans = 0
    # 遍历t
    for index, val in enumerate(t):
        # 如果这一位不是M的整数被， 那么说明， k 次的数这个位置为1
        # 记录下来
        if val % M != 0:
            # 1 << index 左移， 001 010 100
            # k 此位为1
            ans = ans | (1 << index)
    return ans


if __name__ == "__main__":

    # 对数器测试
    M = random.randint(2, 4) # M 的个数
    K = random.randint(1, M - 1) # K 的个数
    k_data = random.randint(0, 1000) # k 的值
    # 测试1000 组数据
    for x in range(1000):
        arr = []
        for i in range(K):
            arr.append(k_data)
        count_M = random.randint(M, M + 10) # count_M 个 次数为M的值
        # 添加次数位 M 的值， 添加 count_M 个
        for i in range(count_M):
            M_data = random.randint(0, 100)
            for j in range(M):
                arr.append(M_data)
        # 寻找值
        ans = find_k(arr, M)
        if k_data != ans:
            print("失败",arr, k_data, ans)
            break
    

    # ans = find_k(arr, M)
    
    # if k_data != ans:
    #     print("失败",arr, k_data, ans)

# 0010
# 0010
# 0101

# 0121
